#!/bin/env python

class StackItem:
    def __init__(self, symbol, state): (self.symbol, self.state) = (symbol, state)
    def __repr__(self): return repr(self.state) + "\n" + repr(self.symbol)

class Action:
    def go(self, stack, input, ctxt): raise AbstractMethodError(self, self.go)

class Init(Action):
    def __init__(self, state): self.state = state
    def __repr__(self): return "Init: " + repr(self.state.id)
    def go(self, stack, input, ctxt):
        stack.append(StackItem(None, self.state))
        return True

class Ignore(Action):
    def __repr__(self): return "Ignore:"
    def go(self, stack, input, ctxt):
        input.move()
        return True

class Shift(Init):
    def __repr__(self): return "Shift: " + repr(self.state.id)
    def goto(self, symbol, stack): stack.append(StackItem(symbol, self.state))

    def go(self, stack, input, ctxt):
        self.goto(input.symbol(), stack)
        input.move()
        return True

class Reduce(Action):
    def __init__(self, rule): self.rule = rule
    def __repr__(self): return "Reduce: " + repr(self.rule)
    def go(self, stack, input, ctxt):
        s = self.rule.apply(stack, ctxt)
        stack[-1].state.action(s.type).goto(s, stack)
        return True

class Accept(Action):
    def __init__(self, rule): pass
    def __repr__(self): return "Accept:"
    def go(self, stack, input, ctxt): return False

class Conflict(Exception):
    def __init__(self, n, o, look): Exception.__init__(self, "Conflict: " + repr(n) + " vs " + repr(o) + " on " + repr(look))

class ParserState:
    def __init__(self, id, ign = set()):
        self.id      = id
        self.actions = {}
        for s in ign: self.actions[s] = Ignore()

    def __repr__(self) : return repr(self.id) + " " + repr(self.actions)
    def __rrepr__(self) : return repr(self.id) + " " + repr(self.actions)

    def addAction(self, look, action):
        if self.actions.has_key(look): raise Conflict(action, self.actions[look], look)
        self.actions[look] = action

    def action(self, look): return self.actions[look]

class Parser:
    def __init__(self, start, lexer):
        self.start = start
        self.input = lexer

    def parse(self, reader, context):
        try:
            self.input.open(reader)
            stack  = []
            action = Init(self.start)
            while action.go(stack, self.input, context): action = stack[-1].state.action(self.input.look())
            return stack[-1].symbol.get()
        except KeyError : raise SyntaxError("Unexpected " + repr(self.input) + ":" + repr(stack[-1]))
